We investigate the problem of computing a minimum set of solutions thatapproximates within a specified accuracy $\epsilon$ the Pareto curve of amultiobjective optimization problem. We show that for a broad class ofbi-objective problems (containing many important widely studied problems suchas shortest paths, spanning tree, and many others), we can compute inpolynomial time an $\epsilon$-Pareto set that contains at most twice as manysolutions as the minimum such set. Furthermore we show that the factor of 2 istight for these problems, i.e., it is NP-hard to do better. We present upperand lower bounds for three or more objectives, as well as for the dual problemof computing a specified number $k$ of solutions which provide a goodapproximation to the Pareto curve.
展开▼
机译：我们研究了计算最小解集的问题，该最小解集在指定精度$ \ epsilon $多目标优化问题的Pareto曲线内近似。我们显示出，对于一类广泛的双目标问题（包含许多重要的，经过广泛研究的问题，例如最短路径，生成树等），我们可以计算多项式时间，其\ε\ -Pareto集最多包含两倍的解决方案。作为最低设置。此外，我们证明了针对这些问题的2因子是正确的，即NP很难做得更好。我们给出了三个或更多目标的上限和下界，以及计算指定数量$ k $的解的双重问题，这些解提供了与Pareto曲线的良好近似。
展开▼
